/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/jump-game-ii
   @Language: C++
   @Datetime: 16-02-09 05:55
   */
class Solution {
public:
	/**
	 * @param A: A list of lists of integers
	 * @return: An integer
	 */
	int jump(vector<int> A) {
		// wirte your code here
		int maxpos=0, curpos=0, step=0;
		for(int i=0; i<A.size(); ++i){
			if (i>maxpos) return -1;
			if (i>curpos){  // need jump
				curpos = maxpos;
				++step;
			}
			maxpos = max(maxpos,i+A[i]);
		}
		return step;
	}
};
